package likou.jindian;

import java.util.HashSet;
import java.util.Set;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/24 05:42
 */
public class _02_08 {
    public static void main(String[] args) {

    }
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head!=null){
            if(set.contains(head)){
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }
    public ListNode detectCycle2(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (true){
            if (fast==null||fast.next==null){
                return null;
            }
            fast = fast.next.next;
            slow=slow.next;
            if (fast==slow){
                break;
            }
        }
        fast=head;
        while (fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}
